package LeetCode.month03.day80;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author 16778
 * @date 2025/10/20 15:02
 * @description
 */
public class No909 {
    //{1,1,-1},{1,1,1},{-1,1,1}
    //{-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1,-1},{-1,35,-1,-1,13,-1},{-1,-1,-1,-1,-1,-1},{-1,15,-1,-1,-1,-1}
    //{2,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1}
    //{-1,10,-1,15,-1},{-1,-1,18,2,20},{-1,-1,12,-1,-1},{2,4,11,18,8},{-1,-1,-1,-1,-1}
    static void main() {
        System.out.println(snakesAndLadders(new int[][]{{-1,10,-1,15,-1},{-1,-1,18,2,20},{-1,-1,12,-1,-1},{2,4,11,18,8},{-1,-1,-1,-1,-1}}));
    }

    public static int snakesAndLadders(int[][] board) {
        int n = board.length;
        int[] arr = new int[n*n+1];
        int index =1;
        boolean flag = true;
        for (int i = n - 1; i >= 0; i--) {
            if(flag){
                for (int j = 0; j < n; j++) {
                    arr[index++] = board[i][j];
                }
            }else{
                for (int j = n-1; j >= 0; j--) {
                    arr[index++] = board[i][j];
                }
            }
            flag = !flag;
        }

        int[] visited = new int[n*n+1];
        int res = 0;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        visited[1]=1;
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int x = queue.poll();
                if(x==n*n) return res;
                for (int j = 1; j <=6 && x+j<n*n+1 ; j++) {
                    int next = x+j;
                    if(arr[next]!=-1){
                        next = arr[next];
                    }
                    if(visited[next]==0){
                        visited[next]=1;
                        queue.add(next);
                    }
                }
            }
            res++;
        }
        return -1;
    }

    public int snakesAndLadders2(int[][] board){
        int n = board.length;
        // 将二维棋盘转换为一维数组，索引0对应位置1
        int[] arr = new int[n * n + 1];
        int index = 1;
        boolean flag = true;

        // 从最后一行开始，蛇形填充
        for (int i = n - 1; i >= 0; i--) {
            if (flag) {
                for (int j = 0; j < n; j++) {
                    arr[index++] = board[i][j];
                }
            } else {
                for (int j = n - 1; j >= 0; j--) {
                    arr[index++] = board[i][j];
                }
            }
            flag = !flag;
        }

        // BFS搜索
        boolean[] visited = new boolean[n * n + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        visited[1] = true;

        int moves = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int current = queue.poll();

                // 如果到达终点
                if (current == n * n) {
                    return moves;
                }

                // 掷骰子1-6
                for (int step = 1; step <= 6 && current + step <= n * n; step++) {
                    int next = current + step;

                    // 处理蛇或梯子
                    if (arr[next] != -1) {
                        next = arr[next];
                    }

                    // 如果未访问过，加入队列
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.add(next);
                    }
                }
            }
            moves++;
        }

        return -1;
    }
}
